package MyBinaryTree;

public class BiTree {
    // 基于二叉链式存储实现

    // 二叉树的头结点
    private BiTreeNode root;

    public BiTree() {
        root = null;
    }

    public BiTree(BiTreeNode root) {
        this.root = root;
    }


    /**
     * 利用中序与先序构建二叉树
     * @param preOrder 先序遍历
     * @param inOrder  中序遍历
     * @param pre  先序遍历的起点
     * @param in   中序遍历的起点
     * @param n    结点的个数
     */
    public BiTree(String preOrder, String inOrder, int pre, int in, int n){
        // 有结点信息
        if(n > 0){
            // 拿到根节点
            char data = preOrder.charAt(pre);
            int i = 0;
            for(; i<n; i++){
                // 寻找一个与根节点相同的结点，此时在中序中，左边是左子树，右边是右子树
                // i+in 就是来对左右子树进行区分查找
                if(inOrder.charAt(i+in)==data){
                    break;
                }
            }
            BiTreeNode root = new BiTreeNode(data);
            // 寻找左子树
            root.lchild = new BiTree(preOrder, inOrder, pre+1, in, i).root;
            // 寻找右子树
            root.rchild = new BiTree(preOrder, inOrder, pre+i+1, in+i+1, n-i-1).root;
        }
    }


    /**
     * 标明空子树的的先序遍历构建二叉树
     * @param preOrder  先序遍历
     * @param i         先序遍历的起始位置
     */
    public BiTree(String preOrder, int i){
        // i是常数0
        char c = preOrder.charAt(i);
        if(c != '#'){
            root=new BiTreeNode(c);
            root.lchild = new BiTree(preOrder, ++i).root;
            root.rchild = new BiTree(preOrder, ++i).root;
        }else{
            root = null;
        }
    }


}
